"""各种排序算法"""
import random


def selection_sort(arr):
    """选择排序"""
    """算法的时间复杂度O(N^2)"""
    length = len(arr)
    for i in range(length):
        min_index = i  # 将当前位置记录为最小位置
        for j in range(i + 1, length):
            if arr[j] < arr[min_index]:  # 和最小位置的数比较
                min_index = j  # 比最小位置的还小，就更新最小位置的索引
        arr[i], arr[min_index] = arr[min_index], arr[i]  # 最小值和i位置对换


def insertion_sort(arr):
    """这插入排序"""
    """算法的时间复杂度O(N^2)"""
    length = len(arr)
    for i in range(length):
        for j in range(i - 1, -1, -1):  # 从i-1开始向前到0
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 如果比前一个位置的值小，交换位置
            else:
                break  # 如果比前一个位置大，说明已经排序完成，跳出循环


def merge_sort(arr):
    return _merge_sort(arr, 0, len(arr) - 1)


def _merge_sort(arr, begin, end):
    """对arr中[begin, end]范围内的数进行排序（包含begin和end）"""
    if end - begin <= 7:
        _insertion_sort_for_other_sort(arr, begin, end)
        return

    mid = begin + (end - begin) // 2

    _merge_sort(arr, begin, mid)
    _merge_sort(arr, mid + 1, end)

    if arr[mid] > arr[mid + 1]:
        _merge(arr, begin, mid, end)


def merge_sort_b2u(arr):
    n = len(arr)
    sz = 1
    while sz <= n:
        i = 0
        while i + sz < n:
            _merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n - 1))
            i += sz + sz
        sz += sz


def _merge(arr, begin, mid, end):
    tem = [arr[x] for x in range(begin, end + 1)]

    i = begin
    j = mid + 1
    for k in range(begin, end + 1):
        if i > mid:
            arr[k] = tem[j - begin]
            j += 1
        elif j > end:
            arr[k] = tem[i - begin]
            i += 1
        elif tem[i - begin] < tem[j - begin]:
            arr[k] = tem[i - begin]
            i += 1
        else:
            arr[k] = tem[j - begin]
            j += 1


def _insertion_sort_for_other_sort(arr, begin, end):
    for i in range(begin + 1, end + 1):
        j = i - 1
        while j >= begin:
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                j -= 1
            else:
                break


def quick_sort(arr):
    _help_qs(arr, 0, len(arr) - 1)


def _help_qs(arr, begin, end):
    if end - begin <= 7:
        _insertion_sort_for_other_sort(arr, begin, end)
        return

    # partition
    lt, gt = _partition_three_ways(arr, begin, end)

    _help_qs(arr, begin, lt)
    _help_qs(arr, gt, end)


def _partition(arr, begin, end):
    # partition操作， j表示小于V的区域的最后一个元素，也是两个区域的分界线
    j = begin

    # 为了尽可能小概率的退化成O(n^2)，采用随机数的方法确定V,然后将v替换到数组开头
    v = random.randint(begin, end)
    arr[begin], arr[v] = arr[v], arr[begin]

    for i in range(begin + 1, end + 1):
        if arr[i] < arr[begin]:
            arr[i], arr[j + 1] = arr[j + 1], arr[i]
            j += 1
    arr[begin], arr[j] = arr[j], arr[begin]

    return j


def _partition2(arr, begin, end):
    i = begin + 1
    j = end

    v = random.randint(begin, end)
    arr[begin], arr[v] = arr[v], arr[begin]

    while True:
        while i <= end and arr[i] < arr[begin]:
            i += 1
        while j > i and arr[j] > arr[begin]:
            j -= 1
        if i > j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        i, j = i + 1, j - 1
    arr[begin], arr[j] = arr[j], arr[begin]
    return j


def _partition_three_ways(arr, begin, end):
    v = random.randint(begin, end)
    arr[begin], arr[v] = arr[v], arr[begin]

    lt = begin
    gt = end + 1
    i = begin + 1
    while i < gt:
        if arr[i] < arr[begin]:
            arr[i], arr[lt + 1] = arr[lt + 1], arr[i]
            lt += 1
            i += 1
        elif arr[i] > arr[begin]:
            arr[i], arr[gt - 1] = arr[gt - 1], arr[i]
            gt -= 1
        else:
            i += 1

    arr[begin], arr[lt] = arr[lt], arr[begin]
    lt -= 1
    return lt, gt
